package com.wenzhi.java_join_kotlin.service.impl

import com.wenzhi.java_join_kotlin.service.IMinCostTicketsService

class MinCostTicketsServiceImpl: IMinCostTicketsService {
    private var days: IntArray? = null
    private var costs: IntArray? = null
    private var memo: IntArray? = null
    private val durations = intArrayOf(1, 7, 30)

    override fun minCostTickets(days: IntArray, costs: IntArray): Int {
        this.days = days
        this.costs = costs
        memo = IntArray(days.size) { Int.MAX_VALUE }
        return dp(0)
    }

    private fun dp(i: Int): Int {
        if (i >= days!!.size) {
            return 0
        }
        if (memo!![i] != Int.MAX_VALUE) {
            return memo!![i]
        }
        memo!![i] = Int.MAX_VALUE
        var j = i
        for (k in 0..2) {
            while (j < days!!.size && days!![j] < days!![i] + durations[k]) {
                j++
            }
            memo!![i] = Math.min(memo!![i], dp(j) + costs!![k])
        }
        return memo!![i]
    }
}
